package main

import "fmt"

func countBadPairs(nums []int) int64 {
	mp := make(map[int]int)
	var res int64 = 0
	for i := 0; i < len(nums); i++ {
		key := nums[i] - i
		// TODO 不理理解
		res += int64(i - mp[key])
		// num[i] - i 相同的个数
		mp[key]++
	}
	return res
}

// 基本思路：我们用哈希表去统计每一个 nums[i]−i 的个数，并在从左到右遍历 i 的过程中计算与之不同的个数，将其累加到答案中。遍历结束后可得题目所求。
// 以代码中的例子 nums := []int{4, 1, 3, 3} 为例：

// - 当 i = 0 时： nums[0] - 0 = 4 ，前面没有元素，所以 mp[4] = 0 ，贡献 0 - 0 = 0 个坏数对
// - 当 i = 1 时： nums[1] - 1 = 0 ，前面 nums[0] - 0 = 4 ，所以 mp[0] = 0 ，贡献 1 - 0 = 1 个坏数对
// - 当 i = 2 时： nums[2] - 2 = 1 ，前面没有相同的差值，所以 mp[1] = 0 ，贡献 2 - 0 = 2 个坏数对
// - 当 i = 3 时： nums[3] - 3 = 0 ，前面 nums[1] - 1 = 0 ，所以 mp[0] = 1 ，贡献 3 - 1 = 2 个坏数对
// 总共有 0 + 1 + 2 + 2 = 5 个坏数对。
// 总结来说， i - mp[key] 就是当前位置 i 与前面所有位置中，那些 nums[位置] - 位置 值与当前位置不同的位置所形成的坏数对的数量。
func main() {
	nums := []int{4, 1, 3, 3}
	count := countBadPairs(nums)
	fmt.Println(count)
}
